﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TSP
{
    class Matrix
    {

        public class Edge
        {
            private int start;
            private int end;

            public Edge(int start, int end)
            {
                this.start = start;
                this.end = end;
            }

            public int Start
            {
                get { return start; }
            }

            public int End
            {
                get { return end; }
            }
        }

        private int[] entered;
        private int[] exited;
        private double[,] costMatrix;
        private double costSoFar;
        private bool completed = false;
        public bool isCompleted() { return this.completed; }

        /// <summary>
        /// Creates the cost matrix, and reduces it
        /// </summary>
        /// <param name="cities">cities on the map</param>
        public Matrix(City[] cities)
        {
            costMatrix = new double[cities.Length, cities.Length];

            for (int i = 0; i < cities.Length; ++i)
            {
                for (int j = 0; j < cities.Length; ++j)
                {
                    double tmpCost = cities[i].costToGetTo(cities[j]);
                    if (tmpCost < 0 || i == j)
                        tmpCost = -1;
                    costMatrix[i, j] = tmpCost;
                }
            }
            costSoFar = 0;
            this.entered = new int[cities.Length];
            for (int i = 0; i < cities.Length; ++i)
                this.entered[i] = -1;
            this.exited = new int[cities.Length];
            for (int i = 0; i < cities.Length; ++i)
                this.exited[i] = -1;
            reduce();
        }

        private enum Status { COMPLETE, ALMOST_COMPLETE, INCOMPLETE}
        /// <summary>
        /// Whether or not every node has been entered and exited
        /// </summary>
        /// <returns></returns>
        private Status computeComplete()
        {
            Status status = Status.COMPLETE;
            int exitCount = 0;
            int enterCount = 0;
            for (int i = 0; i < costMatrix.GetLength(0); ++i)
            {
                if (exited[i] == -1)
                    exitCount++;
                if (entered[i] == -1)
                    enterCount++;
            }
            if (exitCount == 1 && enterCount == 1)
                status = Status.ALMOST_COMPLETE;
            else if (exitCount > 0 || enterCount > 0)
                status = Status.INCOMPLETE;
            return status;
        }

        /// <summary>
        /// copies the other matrix, includes or excludes an edge, removes cycles, and reduces the matrix
        /// </summary>
        /// <param name="other">current matrix</param>
        /// <param name="edge">included/excluded edge</param>
        /// <param name="include">whether to include of exclude the edge</param>
        public Matrix(Matrix other, Edge edge, bool include)
        {
            costSoFar = other.costSoFar;
            costMatrix = (double[,])other.costMatrix.Clone();
            entered = (int[])other.entered.Clone();
            exited = (int[])other.exited.Clone();

            if (include)
            {
                entered[edge.End] = edge.Start;
                exited[edge.Start] = edge.End;
                for (int col = 0; col < costMatrix.GetLength(1); ++col)
                    costMatrix[edge.Start, col] = -1;
                for (int row = 0; row < costMatrix.GetLength(0); ++row)
                    costMatrix[row, edge.End] = -1;
                // set completed or remove cycles
                Status status = computeComplete();
                if (status == Status.COMPLETE)
                    completed = true;
                else if (status == Status.INCOMPLETE)
                    removeCycles(edge.Start, edge.End);
            }
            else
            {
                costMatrix[edge.Start, edge.End] = -1;
            }
            reduce();
        }

        /// <summary>
        /// Removes cycles when an edge is added
        /// </summary>
        /// <param name="i">start city</param>
        /// <param name="j">end city</param>
        private void removeCycles(int i, int j)
        {
            int start = i; 
            int end = j; 
            // The new edge may be part of a partial solution.  Go to the end of that solution.  
            while (exited[end] != -1) 
                end = exited[end]; 
            // Similarly, go to the start of the new partial solution.  
            while (entered[start] != -1) 
                start = entered[start];
            // Delete the edges that would make partial cycles
            while (start != j) 
            {
                costMatrix[end, start] = -1; 
                costMatrix[j, start] = -1; 
                start = exited[start]; 
            }
        }

        /// <summary>
        /// Reduces the rows and columns in the matrix
        /// </summary>
        private void reduce()
        {
            for (int r = 0; r < costMatrix.GetLength(0); ++r)
            {
                if (exited[r] == -1)
                    reduceRow(r);
            }
            for (int c = 0; c < costMatrix.GetLength(1); ++c)
            {
                if (entered[c] == -1)
                    reduceColumn(c);
            }
        }

        /// <summary>
        /// reduces a column
        /// </summary>
        /// <param name="c">the column to be reduced</param>
        private void reduceColumn(int c)
        {
            // find the min
            double min = costMatrix[0, c];
            for (int r = 1; r < costMatrix.GetLength(0); ++r)
                min = getMin(min, costMatrix[r, c]);
            // subtract the min
            for (int r = 0; min != 0 && r < costMatrix.GetLength(0); ++r)
                costMatrix[r, c] = subtractValue(costMatrix[r, c], min);
            // add to total cost
            addToCost(min);
        }

        /// <summary>
        /// reduces the row
        /// </summary>
        /// <param name="r"> the row to be reduced</param>
        private void reduceRow(int r)
        {
            // find the min
            double min = costMatrix[r, 0];
            for (int c = 1; c < costMatrix.GetLength(1); ++c)
                min = getMin(min, costMatrix[r, c]);
            // subtract the min
            for (int c = 0; min != 0 && c < costMatrix.GetLength(1); ++c)
                costMatrix[r, c] = subtractValue(costMatrix[r, c], min);
            // add to total cost
            addToCost(min);
        }

        // the following methods are necessary because -1 == infinity
        private double subtractValue(double variable, double subtractMe)
        {
            if (variable < 0)
                return variable;
            else
                return variable - subtractMe;
        }

        private void addToCost(double val)
        {
            if (val < 0)
                costSoFar = val;
            else
                costSoFar += val;
        }

        private double getMin(double a, double b)
        {
            if (a < 0)
                return b;
            else if (b < 0)
                return a;
            else
                return Math.Min(a, b);
        }

        public int Cost { get { return (int) this.costSoFar; } }

        /// <summary>
        /// returns all of the edges with zero cost
        /// </summary>
        /// <returns>list of edges with zero cost</returns>
        internal List<Edge> getZeroEdges()
        {
            List<Edge> edges = new List<Edge>();

            for (int r = 0; r < costMatrix.GetLength(0); ++r)
            {
                for (int c = 0; c < costMatrix.GetLength(1); ++c)
                {
                    if (costMatrix[r, c] == 0)
                        edges.Add(new Edge(r, c));
                }
            }
            return edges;
        }

        /// <summary>
        /// retruns the completed route
        /// </summary>
        /// <returns>the completed route</returns>
        internal List<int> getRoute()
        {
            List<int> cities = new List<int>();
            int start = 0;
            cities.Add(start);
            int currentCity = exited[start];
            while (currentCity != start)
            {
                cities.Add(currentCity);
                currentCity = exited[currentCity];
            }
            return cities;
        }
    }
}
